

<!DOCTYPE html>

<html>
  <head>
    <meta charset="utf-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Segmented Stacks in LLVM &#8212; LLVM 9 documentation</title>
    <link rel="stylesheet" href="_static/llvm-theme.css" type="text/css" />
    <link rel="stylesheet" href="_static/pygments.css" type="text/css" />
    <script id="documentation_options" data-url_root="./" src="_static/documentation_options.js"></script>
    <script src="_static/jquery.js"></script>
    <script src="_static/underscore.js"></script>
    <script src="_static/doctools.js"></script>
    <script src="_static/language_data.js"></script>
    <link rel="index" title="Index" href="genindex.html" />
    <link rel="search" title="Search" href="search.html" />
    <link rel="next" title="TableGen Fundamentals" href="TableGenFundamentals.html" />
    <link rel="prev" title="LLVM Link Time Optimization: Design and Implementation" href="LinkTimeOptimization.html" />
<style type="text/css">
  table.right { float: right; margin-left: 20px; }
  table.right td { border: 1px solid #ccc; }
</style>

  </head><body>
<div class="logo">
  <a href="index.html">
    <img src="_static/logo.png"
         alt="LLVM Logo" width="250" height="88"/></a>
</div>

    <div class="related" role="navigation" aria-label="related navigation">
      <h3>Navigation</h3>
      <ul>
        <li class="right" style="margin-right: 10px">
          <a href="genindex.html" title="General Index"
             accesskey="I">index</a></li>
        <li class="right" >
          <a href="TableGenFundamentals.html" title="TableGen Fundamentals"
             accesskey="N">next</a> |</li>
        <li class="right" >
          <a href="LinkTimeOptimization.html" title="LLVM Link Time Optimization: Design and Implementation"
             accesskey="P">previous</a> |</li>
  <li><a href="http://llvm.org/">LLVM Home</a>&nbsp;|&nbsp;</li>
  <li><a href="index.html">Documentation</a>&raquo;</li>

        <li class="nav-item nav-item-this"><a href="">Segmented Stacks in LLVM</a></li> 
      </ul>
    </div>


    <div class="document">
      <div class="documentwrapper">
          <div class="body" role="main">
            
  <div class="section" id="segmented-stacks-in-llvm">
<h1>Segmented Stacks in LLVM<a class="headerlink" href="#segmented-stacks-in-llvm" title="Permalink to this headline">¶</a></h1>
<div class="contents local topic" id="contents">
<ul class="simple">
<li><p><a class="reference internal" href="#introduction" id="id2">Introduction</a></p></li>
<li><p><a class="reference internal" href="#implementation-details" id="id3">Implementation Details</a></p>
<ul>
<li><p><a class="reference internal" href="#allocating-stacklets" id="id4">Allocating Stacklets</a></p></li>
<li><p><a class="reference internal" href="#variable-sized-allocas" id="id5">Variable Sized Allocas</a></p></li>
</ul>
</li>
</ul>
</div>
<div class="section" id="introduction">
<h2><a class="toc-backref" href="#id2">Introduction</a><a class="headerlink" href="#introduction" title="Permalink to this headline">¶</a></h2>
<p>Segmented stack allows stack space to be allocated incrementally than as a
monolithic chunk (of some worst case size) at thread initialization. This is
done by allocating stack blocks (henceforth called <em>stacklets</em>) and linking them
into a doubly linked list. The function prologue is responsible for checking if
the current stacklet has enough space for the function to execute; and if not,
call into the libgcc runtime to allocate more stack space. Segmented stacks are
enabled with the <code class="docutils literal notranslate"><span class="pre">&quot;split-stack&quot;</span></code> attribute on LLVM functions.</p>
<p>The runtime functionality is <a class="reference external" href="http://gcc.gnu.org/wiki/SplitStacks">already there in libgcc</a>.</p>
</div>
<div class="section" id="implementation-details">
<h2><a class="toc-backref" href="#id3">Implementation Details</a><a class="headerlink" href="#implementation-details" title="Permalink to this headline">¶</a></h2>
<div class="section" id="allocating-stacklets">
<span id="id1"></span><h3><a class="toc-backref" href="#id4">Allocating Stacklets</a><a class="headerlink" href="#allocating-stacklets" title="Permalink to this headline">¶</a></h3>
<p>As mentioned above, the function prologue checks if the current stacklet has
enough space. The current approach is to use a slot in the TCB to store the
current stack limit (minus the amount of space needed to allocate a new block) -
this slot’s offset is again dictated by <code class="docutils literal notranslate"><span class="pre">libgcc</span></code>. The generated
assembly looks like this on x86-64:</p>
<div class="highlight-text notranslate"><div class="highlight"><pre><span></span>  leaq     -8(%rsp), %r10
  cmpq     %fs:112,  %r10
  jg       .LBB0_2

  # More stack space needs to be allocated
  movabsq  $8, %r10   # The amount of space needed
  movabsq  $0, %r11   # The total size of arguments passed on stack
  callq    __morestack
  ret                 # The reason for this extra return is explained below
.LBB0_2:
  # Usual prologue continues here
</pre></div>
</div>
<p>The size of function arguments on the stack needs to be passed to
<code class="docutils literal notranslate"><span class="pre">__morestack</span></code> (this function is implemented in <code class="docutils literal notranslate"><span class="pre">libgcc</span></code>) since that number
of bytes has to be copied from the previous stacklet to the current one. This is
so that SP (and FP) relative addressing of function arguments work as expected.</p>
<p>The unusual <code class="docutils literal notranslate"><span class="pre">ret</span></code> is needed to have the function which made a call to
<code class="docutils literal notranslate"><span class="pre">__morestack</span></code> return correctly. <code class="docutils literal notranslate"><span class="pre">__morestack</span></code>, instead of returning, calls
into <code class="docutils literal notranslate"><span class="pre">.LBB0_2</span></code>. This is possible since both, the size of the <code class="docutils literal notranslate"><span class="pre">ret</span></code>
instruction and the PC of call to <code class="docutils literal notranslate"><span class="pre">__morestack</span></code> are known. When the function
body returns, control is transferred back to <code class="docutils literal notranslate"><span class="pre">__morestack</span></code>. <code class="docutils literal notranslate"><span class="pre">__morestack</span></code>
then de-allocates the new stacklet, restores the correct SP value, and does a
second return, which returns control to the correct caller.</p>
</div>
<div class="section" id="variable-sized-allocas">
<h3><a class="toc-backref" href="#id5">Variable Sized Allocas</a><a class="headerlink" href="#variable-sized-allocas" title="Permalink to this headline">¶</a></h3>
<p>The section on <a class="reference internal" href="#allocating-stacklets">allocating stacklets</a> automatically assumes that every stack
frame will be of fixed size. However, LLVM allows the use of the <code class="docutils literal notranslate"><span class="pre">llvm.alloca</span></code>
intrinsic to allocate dynamically sized blocks of memory on the stack. When
faced with such a variable-sized alloca, code is generated to:</p>
<ul class="simple">
<li><p>Check if the current stacklet has enough space. If yes, just bump the SP, like
in the normal case.</p></li>
<li><p>If not, generate a call to <code class="docutils literal notranslate"><span class="pre">libgcc</span></code>, which allocates the memory from the
heap.</p></li>
</ul>
<p>The memory allocated from the heap is linked into a list in the current
stacklet, and freed along with the same. This prevents a memory leak.</p>
</div>
</div>
</div>


            <div class="clearer"></div>
          </div>
      </div>
      <div class="clearer"></div>
    </div>
    <div class="related" role="navigation" aria-label="related navigation">
      <h3>Navigation</h3>
      <ul>
        <li class="right" style="margin-right: 10px">
          <a href="genindex.html" title="General Index"
             >index</a></li>
        <li class="right" >
          <a href="TableGenFundamentals.html" title="TableGen Fundamentals"
             >next</a> |</li>
        <li class="right" >
          <a href="LinkTimeOptimization.html" title="LLVM Link Time Optimization: Design and Implementation"
             >previous</a> |</li>
  <li><a href="http://llvm.org/">LLVM Home</a>&nbsp;|&nbsp;</li>
  <li><a href="index.html">Documentation</a>&raquo;</li>

        <li class="nav-item nav-item-this"><a href="">Segmented Stacks in LLVM</a></li> 
      </ul>
    </div>
    <div class="footer" role="contentinfo">
        &#169; Copyright 2003-2020, LLVM Project.
      Last updated on 2020-09-20.
      Created using <a href="https://www.sphinx-doc.org/">Sphinx</a> 3.2.1.
    </div>
  </body>
</html>